package com.dyz.leetcode._05_sort;

import java.util.Arrays;
import java.util.Random;

public class _912_sortArray {
    //使用工具
    public int[] sortArray(int[] nums) {
        Arrays.sort(nums);
        return nums;
    }
    //归并排序
    public int[] sortArray1(int[] nums) {
        Sortguibin(nums, 0, nums.length-1, new int[nums.length]);
        return nums;
    }

    private void Sortguibin(int[] nums, int lo, int hi, int[] tmp) {
        if(lo>=hi){return;}
        int mid = lo+(hi-lo)/2;
        Sortguibin(nums, lo, mid, tmp);
        Sortguibin(nums, mid+1, hi, tmp);

        //合并
        merge(nums, lo, mid, hi, tmp);
    }

    private void merge(int[] nums, int lo, int mid, int hi, int[] tmp) {
        for(int i = lo; i<=hi; i++){
            tmp[i] = nums[i];
        }

        //合并逻辑
        int i = lo;
        int j = mid+1;
        for(int k=lo; k<=hi; k++){
            if(i==mid+1){
                nums[k] = tmp[j++];
            }else if(j==hi+1) {
                nums[k] = tmp[i++];
            }
            else if(tmp[i]<=tmp[j]){ //如果左边大于右边
                nums[k]=tmp[i++];
            }else {
                nums[k]=tmp[j++];
            }
        }
    }
    //快速排序
    // 快排
    public int[] sortArray2(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int lo, int hi) {
        if (lo >= hi) {return;}
        int index = partition(nums, lo, hi);
        quickSort(nums, lo, index - 1);
        quickSort(nums, index + 1, hi);
    }
    // 二分切分
    private int partition(int[] nums, int lo, int hi) {
        int i = new Random().nextInt(hi - lo + 1) + lo; // 随机选一个作为 pivot
        swap(nums, i, hi);
        int pivot = nums[hi];
        int less = lo, great = lo;
        for (; great <= hi - 1 ; great++) {
            if (nums[great] < pivot) {
                swap(nums, less, great);
                less++;
            }
        }
        swap(nums, less, hi);
        return less;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
